class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int len = triangle.size();
        int[] arr = new int[len];
        arr[0] = triangle.get(0).get(0);
        //只需要用一个数组滚动的存上一行的最小值,然后更新这个数组就可以了
        for(int i = 1;i<len;i++) {
            //不可以先处理第一个,因为arr是从后往前更新的,处理了第一个更新的时候arr[j-1]==0 时会丢失数据
            //数组的最后一个,因为只能加前一个
            arr[i] = arr[i-1] + triangle.get(i).get(i);
            //不处理最后一个和第一个
            for(int j = i-1;j>0;j--) {
                arr[j] = Math.min(arr[j],arr[j-1])+triangle.get(i).get(j);
            }
            //处理第一个,因为只能加上面的那个,不能加前一个
            arr[0] += triangle.get(i).get(0);
        }
        int min = arr[0];
        for(int i = 1;i<len;i++) {
            min = Math.min(min,arr[i]);
        }
        return min;
    }
    public int minimumTotal1(List<List<Integer>> triangle) {
        int[][] arr = new int[triangle.size()][triangle.size()];
        arr[0][0] = triangle.get(0).get(0);
        int min = Integer.MAX_VALUE;
        for(int i = 1;i<arr.length;i++) {
            arr[i][0] = arr[i-1][0] + triangle.get(i).get(0);
            System.out.print(arr[i][0]+" ");
            for(int j = 1;j<i;j++) {
                arr[i][j] = Math.min(arr[i-1][j]+triangle.get(i).get(j),arr[i-1][j-1]+triangle.get(i).get(j));
            }
            arr[i][i] = arr[i-1][i-1]+triangle.get(i).get(i);
        }
        for(int i = 0;i<triangle.size();i++) {
            min = Math.min(arr[triangle.size()-1][i],min);
        }
        return min;
    }
}